// 插入排序

public class Insertion {
    public static void sort(Comparable[] a){
        // 插入排序
        int n = a.length;
        for (int i = 1; i < n; i++){
            Comparable temp = a[i];
            int j = i;
            while(j >= 1 && less(temp, a[j-1])){
                // 将比当前元素大的值往后移位
                a[j] = a[j-1];
                j--;
            }
            a[j] = temp;
        }
    }


    private static boolean less(Comparable v, Comparable w){
        return v.compareTo(w) < 0;
    }
}